package com.leetcode.algorithm.y22.m06;

/**
 * 221. 最大正方形
 * 
 * https://leetcode.cn/problems/maximal-square/
 * 
 * @author jie.deng
 *
 */
class Question0221Solution01 {
	
	public int maximalSquare(char[][] matrix) {
		int rows = matrix.length;
		int cols = matrix[0].length;

		// DP状态定义
		int[][] dp = new int[rows][cols];

		int maxLen = 0;
		// DP状态初始化
		// 第一行
		for (int col = 0; col < cols; col++) {
			dp[0][col] = matrix[0][col] == '1' ? 1 : 0;
			if (dp[0][col] > maxLen) {
				maxLen = dp[0][col];
			}
		}
		// 第一列
		for (int row = 0; row < rows; row++) {
			dp[row][0] = matrix[row][0] == '1' ? 1 : 0;
			if (dp[row][0] > maxLen) {
				maxLen = dp[row][0];
			}
		}

		// 状态转移方程
		for (int row = 1; row < rows; row++) {
			for (int col = 1; col < cols; col++) {
				dp[row][col] = matrix[row][col] == '0' ? 0
						: 1 + Math.min(Math.min(dp[row - 1][col], dp[row][col - 1]), dp[row - 1][col - 1]);
				if (dp[row][col] > maxLen) {
					maxLen = dp[row][col];
				}
			}
		}

		return maxLen * maxLen;
	}
    
}